package Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class DijstraAlgorithm {
    public static void main(String[] args) {
        int vertexNum = 5;
        char[] vertexs = new char[] { 'A', 'B', 'W', 'Y', 'C' };
        int[][] matrix = new int[][] { { 0, 10, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 5 },
                { Integer.MAX_VALUE / 2, 5, 1, Integer.MAX_VALUE / 2, 5 },
                { Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 0, 4, Integer.MAX_VALUE / 2 },
                { 7, Integer.MAX_VALUE / 2, 6, 7, Integer.MAX_VALUE / 2 },
                { Integer.MAX_VALUE / 2, 3, 9, 2, 5 } };
        Graph g = new Graph(vertexNum, vertexs, matrix);
        Scanner sc = new Scanner(System.in);
        int srcIndex;
        do{
            System.out.print("索引原点为:");
            srcIndex = sc.nextInt();
        }while(srcIndex < 0 || srcIndex > 4);
        System.out.println(g.vertexs[srcIndex] + "为原点");
        Info info = dijkstra(g, srcIndex);
        for(int i : info.pathSerials){
            System.out.print(g.vertexs[i] + " ");
        }
        System.out.println();
        int index = 0;
        for(int[] path : info.paths){
            for(int i : path){
                System.out.print(g.vertexs[i]);
            }
            System.out.println(": " + info.distances[index++]);
        }
        sc.close();
    }

    public static Info dijkstra(Graph g, int srcIndex) {
        if(srcIndex < 0 || srcIndex >= g.vertexNum){
            return null;
        }
        int[] pathSerials = new int[g.vertexNum];
        int[] path = new int[g.vertexNum];
        int index = 0;
        pathSerials[index] = srcIndex;
        g.visited[srcIndex] = true;
        Arrays.fill(path, -1);
        int[] distances = new int[g.vertexNum];
        for (int i = 0; i < g.vertexNum; i++) {

            distances[i] = g.matrix[srcIndex][i];
        }
        int minIndex = srcIndex;
        while (minIndex != -1) {
            index++;
            for (int i = 0; i < g.vertexNum; i++) {
                if (!g.visited[i]) {
                    distances[i] = Math.min(distances[i], distances[minIndex] + g.matrix[minIndex][i]);
                    if(distances[i] == distances[minIndex] + g.matrix[minIndex][i] && distances[i] != Integer.MAX_VALUE / 2){ // distances[i] != Integer.MAX_VALUE / 2表示仍不可达，就没有前驱
                        path[i] = minIndex;
                    }
                }
            }
            minIndex = indexOf(g, distances);
            if(minIndex == -1){
                break;
            }
            pathSerials[index] = minIndex;
            g.visited[minIndex] = true;
        }
        return new Info(distances, pathSerials, getPathOfAll(path, pathSerials));
    }

    public static int indexOf(Graph g, int[] distances) {
        int min = Integer.MAX_VALUE / 3;
        int minIndex = -1;
        for(int i = 0; i < g.vertexNum; i++){
            if(!g.visited[i]){
                if(distances[i] < min){
                    min = distances[i];
                    minIndex = i;
                }
            }
        }
        return minIndex;
    }

    public static int[] getPath(int[] path, int i){
        Stack<Integer> s = new Stack<Integer>();
        s.push(i);
        int pre = path[i];
        while(pre != -1){
            s.push(pre);
            pre = path[pre];
        }
        int size = s.size();
        int[] pathOfVertex = new int[size];
        while(!s.isEmpty()){
            pathOfVertex[size - s.size()] = s.pop();
        }
        return pathOfVertex;
    }

    public static ArrayList<int[]> getPathOfAll(int[] path, int[] pathSerials){
        ArrayList<int[]> paths = new ArrayList<int[]>();
        for(int i = 0; i < pathSerials.length; i++){
            paths.add(getPath(path, i));
        }
        return paths;
    }

    public static class Graph{
        private int vertexNum;
        private char[] vertexs;
        private int[][] matrix;
        private boolean visited[];

        public Graph(int vertexNum, char[] vertexs, int[][] matrix){
            this.vertexNum = vertexNum;
            this.vertexs = vertexs;
            this.matrix = matrix;
            visited = new boolean[vertexNum];
        }
    }

    public static class Info{
        private int[] distances;
        private int[] pathSerials;
        private ArrayList<int[]> paths;

        public Info(int[] distances, int[] pathSerials, ArrayList<int[]> paths) {
            this.distances = distances;
            this.pathSerials = pathSerials;
            this.paths = paths;
        }

    }
}
